//
//  27.字符串的排列.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/21.
//

import Foundation
/*
 题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 思路：我们求整个字符串的排列，可以看成两步：⾸先求所有可能出现在第⼀个位置的字符，即把第⼀个字符和后⾯所有的字符交换。⾸先固定第⼀个字符，求后⾯所有字符的排列。这个时候我们仍把后⾯的所有字符分为 两部分：后⾯的字符的第⼀个字符，以及这个字符之后的所有字符。然后把第⼀个字符逐⼀和它后⾯的字符交换。 这个思路，是典型的递归思路。
 */
func offer_27() {
    print(Solution().permutation("abca"))
}

fileprivate class Solution {
    func permutation(_ str: String) -> [String] {
        // write code here
        var strArr = Array(str).map { "\($0)" }
        var result = [String]()
        permutationCore(strArr: &strArr, begin: 0, result: &result)
        return result.sorted()
    }
    
    func permutationCore(strArr: inout [String], begin: Int, result: inout [String]) {
        // 递归结束的条件：第⼀位和最后⼀位交换完成
        if begin == strArr.count {
            result.append(strArr.joined())
            return
        }
        for i in begin..<strArr.count {
            //如果字符串相同，则不交换
            if i != begin && strArr[i] == strArr[begin] {
                continue
            }
            // 交换位置
            strArr.swapAt(begin, i)
            // 递归调⽤，前⾯begin+1的位置不变，后⾯的字符串全排列
            permutationCore(strArr: &strArr, begin: begin + 1, result: &result)
            // 换完还得换回来
            strArr.swapAt(begin, i)
        }
    }
}

